Systems and methods for rank-order error diffusion for rending a digital image are described herein. Halftone images that are received (e.g., scanned) by an image processing system can employ systems and methods with one or more of the features described herein for further processing and/or copying of the image. However, the systems and methods described herein may also be beneficially employed, all or in part, in the processing of images from other sources, including but not limited to, Adobe gray tile, JPEG uncompressed images, scanned line art and anti-aliased images. (Adobe is a registered trademark of Adobe Systems Incorporated.)
Binary halftone images consist of a multitude of tiny marked spots on an unmarked background. The spots are laid out in a grid. For example, the spots are laid out with the structure of a halftone screen. When a halftone image is scanned, for example, during a copying procedure, it is highly unlikely that the locations of marked and unmarked portions of the image exactly coincide with the locations of sensors in the scanning device. Therefore, a marked spot may only be partially in the field of view of a related image sensor. For this and other reasons, such as, limited resolution, edge noise and scatter from prior printing, scanned halftone images tend to include gray edges around the halftone spots or dots. To print such grayed halftones, or grayed halftones from other sources, it is necessary to convert the gray level values of the scanned image into a binary (mark or unmark) form or to correct or remove them.
Several methods for converting grayed images into a binary form are known. For example, images such as these are binarized through thresholding, re-halftoning, and through a variety of error diffusion techniques.
Problems exist with each of these known methods. For example, simple thresholding removes all intermediate gray levels and therefore can introduce an unacceptably large gray error. In re-halftoning, the frequency components of the new halftone screen can combine undesirably with a halftone grid pattern of the original or scanned image to produce objectionable moiré patterns. Conventional error diffusion can usually render a scanned halftone without pattern artifacts. However, conventional error diffuision techniques often produce images with excessive fragmentation of dots. In at least some environments, such as, for example, some xerographic environments, dot or spot fragmentation is to be avoided. Compact dots are more forgiving of non-linearities and process drifts associated with reprographic devices than are tiny dot fragments associated with a diffuse fragmentary dot. For example, a small dimensional offset in the size of a tiny dot fragment represents a larger dot gain error than does the same dimensional offset applied to a large compact dot. Dot gain errors are perceived as errors in lightness or darkness of an image or portions of an image.
The problems of the prior art binarization methods are best illustrated in FIG. 1-FIG. 6.
FIG. 1 represents an original halftoned image that has been scanned into an image processing system resulting in a scanned image 110. The original halftone was made with an eighty-five line per inch, forty-five degree dot screen. That screen beat against a grid pattern of the scanning device. The scanning device grid results from a layout of scanner sensors and a sampling frequency of the scanners. As a result, the scanned image 110 includes a subtle checkerboard moiré pattern 114. Additionally, referring to FIG. 2, (which is a magnified view 210 of a portion 118 of the scanned image of FIG. 1) due to a lack of correlation between the location of original image dots and the location and layout of scanner sensors (among other things), the dots of the scanned image have gray edges 214, where the original image was made up of high contrast black dots on a white background. Referring to FIG. 3 and FIG. 4, simple thresholding can be used to remove the gray edges and maintain dot compactness, as is evident in a magnified view 310 of a portion 410 of a thresholded version 414 of the scanned image 110. However, thresholding has the adverse effect of improving the contrast of the subtle moiré pattern 114 thereby generating a clearer and more distinct moiré pattern 418 in the thresholded version 414.
Re-halftoning also maintains dot compactness. However, as will be understood by those of skill in the art, re-halftoning introduces additional moiré effects.
Referring to FIG. 5 and FIG. 6, known error-diffusion techniques such as, for example, Floyd-Steinberg error-diffusion yield an error-diffusion version 510 of the scanned image 110. The error-diffusion version 510 is relatively moiré free. Not only does Floyd-Steinberg error-diffusion not add patterning artifacts to the image, it also reduces the effect of moiré that were present in the scanned image 110. However, as is apparent in a magnified view 610 of a portion 614 of the error-diffusion version 510, error-diffusion introduces dot fragmentation 618 into the image. This dot fragmentation tends to give the image a noisy appearance. Additionally, as explained above, dot fragmentation increases the susceptibility of the image to spatial non-uniformity, temporal instability and dot gain errors of, for example, a rendering device.
Due to the above described problems and limitations of prior art binarization or quantization reduction methods, there has been a desire for a binarization or quantization reduction method that improves or maintains dot compactness while at the same time eliminating, reducing or not contributing to the presence of patterning artifacts in a reduced quantization version of a grayed halftone image or other gray edged images, such as, for example, Adobe gray tile, JPEG uncompressed images, scanned line art and anti-aliased images.